In high-speed networks, routers are required to meet certain quality-of-service requirements associated with communicating network entities. As is known in the art, the quality-of-service is a communication network attribute that exists between two network entities requiring a predetermined network service level. The basic network parameters typically affecting network performance are bandwidth and delays since the application traffic between two network entities in a computer network may require a certain minimum bandwidth or may be sensitive to delays. Thus, in the simplest terms, the quality-of-service means providing consistent and predictable data delivery services to communicating network entities requiring a predetermined level of network service. Further, the quality-of-service is the ability of a network element, such as an application process, host or router to have some level of assurance that its traffic and service requirements can be satisfied.
In general, the quality-of-service elements manage network resources according to application demands and network management settings and, thus, cannot provide certainty that resource sharing occurs. Therefore, quality-of-service with a guaranteed service level requires resource allocation to individual data streams through the network. In current implementations, a priority for quality-of-service developers has been to ensure that resources allocated to the best-effort traffic are not limited after reservations are made. However, equally important is that the high-priority applications do not disable low-priority Internet applications.
The key mechanisms for providing a predetermined level of quality-of-service include an admission control, traffic shaping, packet classification, packet marking and packet scheduling. In quality-of-service enabled Internet Protocol (“IP”) networks, it is necessary to specify a traffic profile for a connection or a set of connections. Traffic shaping or traffic conditioning is typically used, for example, to control the rate of data transmitted out of an interface so that it matches the speed of the remote target interface and, further, to ensure that the traffic conforms to a predetermined policy level. Thus, traffic shaping is primarily used to control the access to available bandwidth, to ensure that traffic conforms to a predetermined set of policies, and to regulate the flow of traffic in order to avoid congestion that can occur if the transmitted traffic exceeds the access speed of its remote, target interface.
Traffic shaping is typically implemented on an edge router or core router and provides a mechanism to control the amount and volume of data being sent into the network as well as the rate at which the data is being sent. The predominant methods for traffic shaping include a leaky bucket method and a token bucket method. The leaky bucket is typically used to control the rate at which data is sent into the network and provides a mechanism by which bursty data can be shaped into a steady data stream. The leaky bucket implementation is typically employed for shaping traffic into flows with a fixed rate of admission into the network and is generally ineffective in providing a mechanism for shaping traffic into flows with variable rates of admission.
The token bucket provides a method for traffic shaping and ingress rate control. The token bucket provides a control mechanism that dictates when data can be transmitted based on the presence of tokens in a bucket and uses network resources by allowing flows to burst up to configurable burst threshold levels. In the token bucket implementation, tokens are “put” into the bucket at a certain rate, and the bucket has a predetermined capacity. In such an implementation, if the bucket fills up to its top capacity, newly arriving tokens are discarded. Similarly, if the bucket is full of tokens, incoming tokens overflow and are not available for future packets. Thus, at any time, the largest burst of data a source can send into a network is roughly proportional to the size of the bucket. In the token burst implementation, a system administrator may configure a token generation rate and a depth of the burst.
In addition to traffic shaping, the token bucket methods may be employed for congestion avoidance. As is known in the art, congestion avoidance refers to methods of controlling an average queue size on an outgoing interface of a router such as an edge router. The primary mechanism used by the token bucket and leaky bucket for shaping the traffic includes dropping the incoming data packets to the network. Some routers handle dropping the packets using a technique typically referred to as tail dropping. Using tail dropping, a router simply drops packets indiscriminately, i.e., without regard to priority or class of service, for example. Other methods that have been used to avoid congestion more effectively than tail dropping include a Random Early Detection (“RED”), a Flow-based Random Early Detection (“FRED”), or a Weighted Random Early Detection (“WRED”).
When RED is not configured, output buffers fill during periods of congestion. When the buffers are full, tail drop occurs, and all additional packets are dropped. Since the packets are dropped all at once, global synchronization of Transmission Control Protocol hosts can occur as multiple hosts reduce their transmission rates. As the congestion clears, the Transmission Control Protocol sources increase their data transmission rates, resulting in waves of congestion followed by periods where the transmission link is not fully used.
The Random Early Detection mechanism controls the data congestion by dropping or marking packets with a drop probability. Typically, an algorithm used by the Random Early Detection mechanism may sample a queue length on a router and compare it to two threshold levels, a low threshold level and a high threshold level. For example, if the queue length is less than the low threshold level, no packets are dropped and packets are forwarded to a destination address. If the queue length is between the low threshold level and the high threshold level, incoming packets are dropped with a probability that is directly proportional to the queue length, and, if the queue length is greater than the high threshold level, all incoming packets are dropped.
The Random Early Detection mechanism reduces the chances of tail dropping by selectively dropping packets when, for example, an output interface begins to show signs of congestion. By dropping some packets early rather than waiting until the buffer is full, Random Early Detection avoids dropping large numbers of packets at once and minimizes the chances of global synchronization.
The Weighted Random Early Detection generally drops packets selectively based on IP precedence so that packets with a higher IP precedence are less likely to be dropped than packets with a lower precedence. In such an implementation, higher priority traffic is delivered with a higher probability than lower priority traffic. The Weighted Random Early Detection is more useful in the core routers of a network, rather than at the edge routers that assign IP precedence to packets as they enter the network.
While the Random Early Detection mechanism and the variation thereof have been widely studied and employed in the existing computer networks, they suffer from a number of disadvantages. The Random Early Detection mechanism as well as the Weighted Random Early Detection mechanism signal the source about the congestion by dropping the packets and have the ability to control only a predetermined type of data, specifically, Transmission Control Protocol data.
Thus, the need remains for a system and method for traffic shaping in computer networks.